package com.njupt.Tree;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/3 16:58
 * @Description: 654. 最大二叉树
 * @Version: 1.0
 */


public class ConstructMaximumBinaryTree {

    public TreeNode constructMaximumBinaryTree(int[] nums) {

        int left = 0;
        int right = nums.length-1;
        boolean[] flag = new boolean[nums.length];
        List<Integer> collect = Arrays.stream(nums).mapToObj(Integer::valueOf).collect(Collectors.toList());
        return buildMaxinumTree(left,right,collect,flag);
    }

    private TreeNode buildMaxinumTree(int left, int right, List<Integer> collect, boolean[] flag) {

        if(left>right) return null;
        Optional<Integer> max = collect.subList(left,right+1).stream().max(Comparator.naturalOrder());
        int maxNum = 0;
        if(max.isPresent()){
           maxNum = max.get();
        }
        TreeNode root = new TreeNode(maxNum);
        int mid = collect.indexOf(maxNum);
        flag[mid] = true;
        int leftIndex = indexOfLeft(flag,mid);
        root.left = buildMaxinumTree(leftIndex,mid-1,collect,flag);
        int rightIndex = indexOfRight(mid,flag);
        root.right = buildMaxinumTree(mid+1,rightIndex,collect,flag);
        return root;
    }

    private int indexOfRight(int mid, boolean[] flag) {
        int i = mid;
        for(i= mid +1 ;i<flag.length;i++){
            if(flag[i] == true){
                return i-1;
            }
        }
        return i-1;
    }

    private int indexOfLeft(boolean[] flag, int mid) {
        int i = mid;
        for (i=mid-1;i>=0;i--){
            if(flag[i] == true){
                return i+1;
            }
        }
        return i+1;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,1,6,0,5};
        ConstructMaximumBinaryTree test = new ConstructMaximumBinaryTree();
        TreeNode root = test.constructMaximumBinaryTree(nums);
        System.out.println();

    }
}
